11339. Разделите на 2 группы

Разделите числа 1, 2, ..., n на две группы так, чтобы абсолютная разность между суммами элементов этих групп была наименьшей из возможных.

Вход. Одно целое число n (2 ≤ n ≤ 10⁵).

Выход. В первой строке выведите два целых числа – количество элементов в первой и второй группах.

Во второй строке выведите элементы первой группы, а в третьей – элементы второй группы.

Элементы внутри каждой группы могут быть выведены в любом порядке. Каждое число от 1 до n должно быть включено ровно в одну из групп.

Пример входа 1	Пример выхода 1
4	2 2 1 4 2 3
Пример входа 2	Пример выхода 2
5	3 2 1 2 4 3 5

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Заметим, что если числа n и n – 3 поместить в одну группу, а n – 1 и n – 2 поместить в другую (сумма чисел в каждой группе будет одинаковой), то задача сведётся к аналогичной задаче меньшей размерности, а именно к разбиению на группы чисел 1, 2, ..., n – 4.

Для n ≤ 3 числа распределим по группам следующим образом:

· Если остаются три числа 1, 2, 3, то их можно разделить на две группы: {1, 2} и {3}.

· Если остаются два числа 1, 2, то разделим их на группы: {1} и {2}. Разность сумм чисел в группах составит 1.

· Если остается одно число 1, то его можно поместить в любую группу. Разность сумм чисел в группах составит 1.

Если сумма всех чисел от 1 до n четная, то их можно разделить на две группы с одинаковой суммой.

Если сумма всех чисел от 1 до n нечетная, то их можно разделить на две группы с разницей сумм, равной 1.

Пример

Пусть n = 10. Числа в группы размещаем следующим образом:

Пусть n = 11. Числа в группы размещаем следующим образом:

Реализация алгоритма

Читаем входное значение n.

scanf("%d", &n);

Устанавливаем начальные суммы чисел в группах s₁ и s₂ равными 0.

s1 = s2 = 0;

Перебираем числа от n до 1 по убыванию.

for (i = n; i > 0; i--)

Если s₁ < s₂, то заносим число i в первую группу. Иначе заносим число i во вторую группу.

if (s1 < s2)

{

s1 += i;

a.push_back(i);

}

else

{

s2 += i;

b.push_back(i);

}

Выводим размеры групп.

printf("%d %d\n", a.size(), b.size());

Выводим числа первой группы.

for (i = 0; i < a.size(); i++)

printf("%d ", a[i]);

printf("\n");

Выводим числа второй группы.

for (i = 0; i < b.size(); i++)

printf("%d ", b[i]);

printf("\n");